\documentclass[11pt,twoside,a4paper]{article}

%\usepackage[french]{babel}
%\usepackage{a4}
\usepackage{fullpage}
%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{float}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage[thinlines,thiklines]{easybmat}
\usepackage{multirow}
\usepackage{algorithmic}
\usepackage{algorithm}

% Style bibliographique
\bibliographystyle{plain}
%--- Definitions de nouvelles commandes ---
\newcommand{\N}{\mathbb{N}} % les entiers naturels
\newcommand{\Z}{\mathbb{Z}} % les entiers relatifs
\newcommand{\Q}{\mathbb{Q}} % les rationnels
\newcommand{\R}{\mathbb{R}} % les rationnels
\newcommand{\F}{\mathbb{F}} % un corps fini
\newcommand{\K}{\mathbb{K}} % un corps
\newcommand{\p}{\mathfrak{p}} % un p gothik
\newcommand{\M}{\mathcal{M}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\OK}{\mathcal{O}_{\K}}
\newcommand{\courbe}{\mathcal{C}} % une courbe avec un joli C
\newcommand{\jac}{\operatorname{Jac}(\mathcal{C})} %la jacobienne
\newcommand{\Nm}{\mathcal{N}}
\newcommand{\ag}{\mathfrak{a}}
\newcommand{\bg}{\mathfrak{b}}
\newcommand{\cg}{\mathfrak{c}}
\newcommand{\dg}{\mathfrak{d}}
\newcommand{\g}{\mathfrak{g}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{heuristic}{Heuristic}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{notation}{Notation}
\newtheorem{example}{Example}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

%\newcommand{\algorithmicreturn}{\textbf{return}}
%--- Pour le titre ---
\title{Polynomial time HNF over $\OK$}
\author{Jean-Fran\c{c}ois Biasse\\Claus Fieker\\Guillaume Quintin}
\date{}
%============================= Corps =================================
\begin{document}
\maketitle            % écrit le titre
%\tableofcontents      % écrit la table des matières

\section{The HNF}

Let $M\subseteq K^l$ be a finitely generated $\OK$-module. As in~\cite[Chap. 1]{cohen2}, we say that $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$, where $a_i\in K$ and $\mathfrak{a}_i$ is a fractional ideal, is a pseudo-basis for $M$ if
$$M = \mathfrak{a}_1a_1\oplus \cdots \oplus \mathfrak{a}_na_n.$$
Note that a pseudo-basis is not unique, and the main result of~\cite{stehle_fieker_LLL} is precisely to compute a pseudo-basis of short elements. If the sum is not direct, we call $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$ a pseudo-generating set for $M$. Once a pseudo-generating set $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$ for $M$ is known, we can associate a pseudo-matrix $A = (A,I)$ to $M$, where $A\in K^{n\times l}$ and $I = (\ag_i)_{i\leq n}$ is a list of $n$ fractional ideals such that 
$$M = \ag_1 A_1 + \cdots +\ag_n A_n,$$
where $A_i\in K^l$ is the $i$-th row of $A$. We can construct a pseudo-basis from a pseudo-generating set by using the Hermite normal form (HNF) over Dedekind domains (see ~\cite[Th. 1.4.6]{cohen2}). Assume $A$ is of rank $l$ (in particular $n\geq l$), then there exists an $n\times n$ matrix $U = (u_{i,j})$ and $n$ non-zero ideals $\bg_1, \cdots , \bg_n$ satisfying 
\begin{enumerate}
 \item $\forall i,j, u_{i,j}\in \bg_i^{-1}\ag_j$.
 \item $\ag = \det(U)\bg$ for $\ag = \prod_i\ag_i$ and $\bg = \prod_i \bg_i$.
 \item The matrix $UA$ is of the form\\
\[ UA = \left( 
   \begin{BMAT}(@)[0.5pt,2cm,2cm]{c}{c.c}
   \begin{BMAT}(e)[1pt,1cm,1cm]{cccc}{cccc}
1      & 0      & \hdots & 0      \\
\vdots & 1      & \ddots & \vdots \\
\vdots & \vdots & \ddots & 0      \\
*      & *      & \hdots & 1\\
  \end{BMAT} \\
\begin{BMAT}[0.5pt,1cm,1cm]{c}{c} 
        (0)
\end{BMAT}
\end{BMAT}
   \right).
\]

 \item $M = \bg_{1}\omega_1\oplus \cdots \oplus \bg_{l}\omega_l$ where $\omega_1,\cdots \omega_l$ are the first $l$ rows of $UA$.
\end{enumerate}

In general, the algorithm of~\cite{cohen2} for computing the HNF of a pseudo-matrix takes exponential time, but as in the integer case, there exists a modular one which is polynomial in the dimensions of $A$, the degree of $K$, and the bit size of the modulo. Note that in the case of a pseudo matrix representing an $\OK$-module $M$, the modulo is an integral multiple of the determinantal ideal $\g(M)$, which is generated by all the ideals of the form 
$$\det_{i_1,\cdots,i_l}(A)\cdot \ag_{i_1}\cdots\ag_{i_l},$$
where $\det_{i_1,\cdots,i_l}(A)$ is the determinant of the $l\times l$ minor consisting of the rows of indices $i_1,\cdots,i_l$. The determinantal ideal is a rather involved structure, except in the case $l = n$.

\section{Notion of size}

To measure the size of an element $x\in K$, we usually take the bit size of
$$T_2(x) := |\sigma_1(x)|^2 + \cdots + |\sigma_d(x)|^2,$$
where $\sigma_1,\cdots,\sigma_d$ are the $d$ complex embeddings of $K$. On the other hand, the size of an ideal usually 
relates to its norm. We choose a notion of size that bounds the bit size required to represent our elements. An ideal 
$I\subset \OK$ is given by the matrix $M^I\in\Z^{d\times d}$ of its basis expressed in an integral basis 
$\omega_1,\cdots,\omega_d$ of $\OK$. If the matrix is in Hermite Normal Form, the size required to store it is therfore bounded by 
$d^2\max_{i,j}\log(|M^I_{i,j}|)$, where $\log(x)$ is the base 2 logarithm of $x$. In the meantime, every coefficient of 
$M^I$ is bounded by $|\det(M^I)|=\Nm(I)$ (see~\cite[Prop. 4.7.4]{cohen}). Thus, we define the size of an ideal as 
$$S(I):= d^2\log(\Nm(I)).$$	
If $\ag = (1/k)I$ is a fractional ideal of $K$, where $I\subset\OK$ and $k\in\Z_{>0}$, then the natural 
generalization of the notion of size is 
$$S(\ag) := \log(k) + S(I),$$
where $\log(k)$ is the base 2 logarithm of $k$.	On the other hand, if $x\in\OK$ can be written as $x = \sum_{i\leq d}x_i\omega_i$, 
where $x_i\in\Z$, then a natural notion of size is 
$$S(x) := d\log(\max_i|x_i|).$$
%$$S(x) := \sum_{i\leq d}\log(|x_i|).$$
It can be generalized to elements $y\in K$ by writing $y = x/k$ where $x\in\OK$ and $k$ is a minimal positive integer, and setting 
$$S(y) := \log(k) + S(x).$$
In the litterature, the size of elements of $K$ is often expressed with $\sqrt{T_2(x)}$. Let us show how $S(x)$ and $\log(\sqrt{T_2(x)})$ are 
related. First, we can assume~\cite[Lem. 1]{stehle_fieker_LLL} that we choose an LLL-reduced integral basis 
$\omega_1,\cdots, \omega_d$ of $\OK$ satisfying 
$$\max_i\sqrt{T_2(\omega_i)}\leq \sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}.$$
Then, we have 
\begin{align*}
\forall i\leq d, |x|_i &= |\sigma_i(x)|\\
&= \left| \sum_{j\leq d} |x_j| \sigma_i(\omega_j)\right|\\
&\leq d\left(\max_i |x_i|\right) \left( \max_j\sqrt{T_2(\omega_j)} \right) 
\leq \left(\max_i |x_i|\right) d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}.
%&\leq S(x) \frac{2^{d^2/2}\sqrt{|\Delta_K|}}{\sqrt{d}}.
\end{align*}
Therefore, $\log\left(\sqrt{T_2(x)}\right)\leq S(x)+ \log\left(d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}\right)$. On the other hand, we know from~\cite[Lem. 2]{stehle_fieker_LLL} that for our choice of an integral basis 
of $\OK$, we have
%the 
%arithmetic-geometric inequality tells us that 
$$\forall x\in\OK, \ S(x)\leq d\log\left(2^{3d/2}\sqrt{T_2(x)}\right).$$
So, for all $x\in \OK$, 
$S(x) = O\left(\log\left( \sqrt{T_2(x)}\right)\right)$, and $\log\left( \sqrt{T_2(x)}\right) = O(S(x))$, 
where the constants are polynomial in $d$ and $\log|\Delta_K|$.

\section{The normalization}

Given a one-dimensional $\OK$-module $\ag A\subseteq\OK^n$ where $\ag$ is a fractional ideal of $K$, and $A\in K^n$, it is 
interesting to find $b\in K$ such that the size taken to represent our module as $(b\ag)(A/b)$ is bounded 
by reasonable values. Indeed, the same module can be represented by elements of arbitrary large size, which 
would cause a significant slow-down in our algorithms.

The first step to our normalization is to make sure that $\ag$ is integral. If $k\in\Z$ is its denominator,
then replacing $\ag$ by $k\ag$ and $A$ by $A/k$ increases the size needed to represent our module via the 
growth of all the denominator of the coefficients of $A\in K^n$. This growth is of 
$$n\log(k).$$ 

We can now assume that our one-dimensional module is of the form $\ag A$ where $\ag\subseteq\OK$ and 
$A\in K^n$ at the price of a slight growth of its size. The next step of normalization is to express our 
module as $\ag' A'$ where $A'\in K^n$ and $\ag'\subseteq\OK$ such that $\Nm(\ag')$ only depends on invariants of 
the field. To do this, we invert $\ag$ and write it as 
$$\ag^{-1} = \frac{1}{k}\bg,$$
where $k\in\Z_{>0}$ and $\bg\subseteq\OK$. As $\Nm(\ag)\in\ag$, we have $\Nm(\ag)\ag^{-1}\subseteq\OK$ and 
thus $k\leq \Nm(\ag)$. Therefore, 
$$\Nm(\bg) \leq \frac{\Nm(k)}{\Nm(\ag)}\leq \frac{k^{d}}{\Nm(\ag)} \leq \Nm(\ag)^{d-1}.$$
Then we use the LLL algorithm to find an element $\alpha\in\bg$ such that
$$\sqrt{T_2(\alpha)} \leq \sqrt{d}2^{d^2/2}|\Delta_K|^{1/2d}\Nm(\bg)^{1/d}.$$
%\begin{align*}
%\sqrt{T_2(\alpha)} &\leq \sqrt{d}2^{d^2/2}|\Delta_K|^{1/2d}\Nm(\bg)^{1/d} \\
%&\leq \sqrt{d}2^{d^2/2}|\Delta_K|^{1/2d}\Nm(\ag).
%\end{align*}
Our reduced ideal is 
$$\ag' := \left(\frac{\alpha}{k}\right)\ag \subseteq \ag^{-1}\ag = \OK.$$
The integrality of $\ag'$ comes from the definition of $\bg^{-1}$ and the fact that $\alpha\in\bg$. From the 
arithmetic-geometric mean, we know that $\Nm(\alpha)\leq T_2(\alpha)^{d/2}/d^d$, therefore 
$$\Nm(\alpha)\leq 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\bg),$$
and the norm of the reduced ideal can be bounded by $\Nm(\ag')\leq 2^{d^3/2}\sqrt{|\Delta_K|}$. On the other 
hand, we set $A' := (k/\alpha)A$, which induces a growth of the coefficients $a_i$ of $A$. Indeed, each 
$a_i$ is multiplied by $(k/\alpha)$. If $y,z\in\OK$, then 
\begin{align*}
S(yz) &\leq d \log\left( 2^{3d/2}\sqrt{T_2(yz)}\right)\\
&\leq d \log\left( 2^{3d/2}\sqrt{T_2(y)T_2(z)} \right) \\
&\leq d \left( \frac{3d}{2} + \log\left(\sqrt{T_2(y)}\right) + \log\left(\sqrt{T_2(z)}\right) \right)\\
&\leq d \log\left(\sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}\right) \left( \frac{3d}{2} + S(y) + S(z) \right)
\end{align*}
So we certainly have 
$$\forall y,z\in K,\  S(yz)\leq \log\left(\sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}\right) \left( \frac{3d}{2} + S(y) + S(z) \right),$$
Wich allows us to state 
$$S\left(a_i\frac{k}{\alpha}\right) \leq  \log\left(\sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}\right)\left(S(a_i) + n\log(k) + S\left(\frac{1}{\alpha}\right)\right).$$
In addition, if $\frac{1}{\alpha} = \frac{x}{k'}$ where $x\in\OK$ and $k'\in\Z_{>0}$, then 
$$S\left(\frac{1}{\alpha}\right)\leq \log(k') + d\log\left(2^{3d/2}\sqrt{T_2(x)}\right).$$
On the one hand, we have 
\begin{align*}
k' &\leq \Nm(\alpha)\\
&\leq 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1},
\end{align*}
and on the other hand, we need to bound $T_2(x)$. We notice that since $\Nm(\alpha)\in\Q$, 
$\forall j\leq d$, $\Nm(\alpha) = \alpha\beta = \sigma_j(\alpha\beta)$. We also know that 
$\forall j$, $\sqrt{T_2(\alpha)}\leq |\sigma_j(\alpha)|$. Therefore, 
$$\forall j\leq d, \ |\sigma_j(x)| = \frac{\Nm(\alpha)}{|\sigma_j(\alpha)|} 
 = \prod_{i\neq j}|\sigma_i(\alpha)|\leq T_2(\alpha)^{(d-1)/2}.$$
This allows us to bound $T_2(x)\leq \sqrt{d}T_2(\alpha)^{d-1}$, and thus
\begin{align*}
S\left( \frac{1}{\alpha}\right) &= \log(k') + S(x) \\
&\leq \log\left(\Nm(\alpha)\right) + \log\left( 2^{3d/2} \sqrt{T_2(x)}\right)\\
&\leq \log\left( 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1}\right) + \log\left( \sqrt{d}2^{3d/2}T_2(\alpha)^{d-1}\right)\\
&\leq \log\left( 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1}\right) +
\log\left(d2^{(d^2+3d)/2}|\Delta_K|^{1/2d}\Nm(\ag)\right)\\
&= \log(d) + \frac{(d^3 + d^2 + 3d)}{2} + \frac{d+1}{2d}\log|\Delta_K| + d\log\Nm(\ag).
\end{align*}
%and on the other hand since $T_2(x)$ is the first minima of $(x)\subseteq\OK$ with respect to $T_2$, we 
%have from Minkowski's first theorem that 
%\begin{align*}
%\sqrt{T_2(x)}&\leq \sqrt{d}\left(\Nm(x)\sqrt{|\Delta|}\right)^{1/d}\\
%&\leq \sqrt{d}\left(\frac{k'^d}{\Nm(\alpha)}\sqrt{|\Delta|}\right)^{1/d}\\
%&\leq \sqrt{d}\left(k'^d\sqrt{|\Delta|}\right)^{1/d}.
%\end{align*}
%Therefore
%$$S\left(\frac{1}{\alpha}\right) \leq \log\left(2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1}\right) + 
%d\log\left(2^{3d/2} \sqrt{d} k'|\Delta|^{1/2d}\right),$$
Therefore, the size $S\left(a_i\frac{k}{\alpha}\right)$ of the normalized vectors of our pseudo-basis is thus polyniomaly bounded by 
$d$, $n$, $\log|\Delta_K|$, $S(a_i)$, and $S(\ag)$. Our normalization was performed at the price of a 
reasonable growth in the size of the object we manipulate.
\begin{algorithm}[ht]
\caption{Normalization of a one-dimensional module}
\begin{algorithmic}[1]\label{alg:normalization}
\REQUIRE $A \in K^{n}$, fractional ideal $\ag$ of $K$.
\ENSURE  $A' \in K^{n}$, $\ag'\subseteq \OK$ such that $\Nm(\ag')\leq 2^{d^3/2}\sqrt{|\Delta_K|}$ and 
$\ag A = \ag' A'$.
\STATE $\ag \leftarrow k_0\ag$, $A \leftarrow A/k_0$ where $k_0$ is the denominator of $\ag$.
\STATE $\bg \leftarrow k \ag^{-1}$ where $k$ is the denominator of $\ag^{-1}$.
\STATE Let $\alpha$ be the first element of an LLL-reduced basis of $\bg$.
\STATE $\ag'\leftarrow \left(\frac{\alpha}{k}\right) \ag$, $A' \leftarrow \left(\frac{k}{\alpha}\right)A$.
\RETURN $\ag'$, $A'$.
\end{algorithmic}
\end{algorithm}

\section{Reduction of an element modulo a fractional ideal}

To achieve a polynomial complexity for our pseudo-HNF algorithm, we need some elements of $K$ modulo 
ideals whose norm can be reasonably bounded. We show in this section how to bound the norm of a reduced 
element with respect to the norm of the ideal and invariants of $K$. Let $\ag$ be a fractional ideal of 
$K$, and $x\in K$. Our goal is to find $\overline{x} \in K$ such that 
$\| \overline{x} \| := \sqrt{T_2(\overline{x})}$ 
is bounded, and that $x - \overline{x} \in \ag$. 

The reduction algorithm consists of finding an LLL-reduced basis $r_1,\cdots , r_d$ of $\ag$ and to decompose 
$$x = \sum_{i\leq d } x_i r_i.$$
Then, we define 
$$\overline{x} := x - \sum_{i\leq d } \lfloor x_i \rceil r_i.$$
Note that two different LLL-reduced basis for $\ag$ will lead to two different $\overline{x}$. One way around this is to apply the LLL algorithm to an HNF basis of $\ag$, which is unique. Now, let us bound the $T_2$-norm of $\overline{x}$. Let $I$ be an integral ideal of $\OK$, and $\lambda_1,\cdots,\lambda_d$ its first $d$ successive minimas. From Minkowski's second theorem, we know that 
$$\prod_{j\leq d} \lambda_j \leq d^{d/2} \Nm(I)\sqrt{\Delta_K}.$$
In the meantime, the arithmetic-geometric mean applied to any $x\in I$ such that $\|x\| = \lambda_1$ implies that 
$$1\leq \Nm(I)^{2/d} \leq \Nm(x)^{2/d} \leq \frac{\|x\|^2}{d}, $$
and thus $\lambda_1 \geq \sqrt{d}\Nm(I)^{1/d}$. So in particular, every $\lambda_i$ has to satisfy 
$$\lambda_i\leq \sqrt{d}\Nm(I)^{1/d}\sqrt{\Delta_K}.$$
The LLL~\cite{LLL} algorithm allows us to compute a basis $(r_j)_{j\leq d}$ for $I$ that satisfies
$$\|r_j\|\leq 2^{d/2}\lambda_i\leq 2^{d/2}\sqrt{d}\Nm(I)^{1/d}\sqrt{\Delta_K}.$$ 
The same holds for a fractional ideal $\ag$ of $K$. Indeed, by definition, there is a $k\in \Z$ such that $I = k\ag$ is an ideal of $\OK$, and if $(r_j)_{j\leq d}$ is an LLL-reduced basis for $\ag$, then $(kr_j)_{j\leq d}$ is an LLL-reduced basis for $I$ and we have 
\begin{align*}
 k\|r_j\| = \|kr_j \| &\leq  2^{d/2}\sqrt{d}\Nm(k\ag)^{1/d}\sqrt{\Delta_K} \\
&\leq  2^{d/2}\sqrt{d}\Nm((k))^{1/d} \Nm(\ag)^{1/d}\sqrt{\Delta_K} \\
&\leq  k\cdot 2^{d/2}\sqrt{d} \Nm(\ag)^{1/d}\sqrt{\Delta_K}.
\end{align*}
Then, as $\lfloor x_j \rceil r_j\leq 1$, we see that 
$$\|\overline{x}\|\leq d\max_j\|r_j\|\leq d^{3/2}2^{d/2}\Nm(\ag)^{1/d}\sqrt{\Delta_K}.$$


\begin{algorithm}[ht]
\caption{Reduction modulo a fractional ideal}
\begin{algorithmic}[1]\label{alg:reduction}
\REQUIRE $x\in K$, fractional ideal $\ag$ of $K$.
\ENSURE  $\overline{x}\in K$ such that $x - \overline{x} \in \ag$ and $\|\overline{x}\| \leq d^{3/2}2^{d/2}\Nm(\ag)^{1/d}\sqrt{\Delta_K}$.
\IF{$\|x\| \leq d^{3/2}2^{d/2}\Nm(\ag)^{1/d}\sqrt{\Delta_K}$ \textbf{or} $x = 1$}
\RETURN $x$.
\ELSE
\STATE Compute an LLL-reduced basis $(r_i)_{i\leq d}$ of $\ag$.
\STATE Decompose $x = \sum_{i\leq d} x_i r_i$.
\STATE $\overline{x} \leftarrow x - \sum_{i\leq d } \lfloor x_i \rceil r_i.$
\RETURN $\overline{x}$.
\ENDIF
\end{algorithmic}
\end{algorithm}


\section{Algorithm}

Let us assume that our module is integral, that is $M \subseteq \OK^n$. 
We use a variant of the modular version of~\cite[Alg. 1.4.7]{cohen2} that ensures that the current 
pseudo-basis $[\ag_i,A_i]_{i\leq n}$ of the module satisfies $\ag\subseteq\OK$ at every step of the 
algorithm. In addition, we use Algorithm~\ref{alg:normalization} to ensure that we know an absolute 
bound on $\Nm(\ag_i)$ at every step. This, combined with reduction steps modulo the determinantal ideal
$\g$, ensures that both the numerator and the denominator of our entries remain bounded throughout the 
algorithm. 

As we assume that our module is integral, we immediatly deduce that the ideal $\dg$ created at Step~6 
of Algorithm~\ref{alg:HNF} is integral as well. In addition, from the definition of the inverse of an ideal 
we also have that 
$$\frac{b_{i,i}\bg_ib_{i,j}\bg_j}{b_{i,j}\bg_j + b_{i,i}\bg_i}\subseteq \OK,$$
which allows us to conclude that the update of $(\bg_i,\bg_j)$ performed at Step~9 of Algorithm~\ref{alg:HNF}
preserves the fact that our ideals are integral. 

The computation of $u\in \bg_i\dg^{-1}$ and $v\in \bg_j\dg^{-1}$ such that $b_{i,j}u+ b_{i,i}v = 1$ at 
Step~7 is achieved by using~\cite[Th. 1.3.3]{cohen2} to obtain $x\in b_{i,j}\bg_i/\dg\subseteq\OK$, and 
 $y\in b_{j,j}\bg_j/\dg \subseteq\OK$, such that $x + y = 1$. We then set 
\begin{align*}
u &\leftarrow x/b_{i,j} \\
v &\leftarrow x/b_{j,j}
\end{align*}

\begin{algorithm}[ht]
\caption{HNF of a full-rank square pseudo-matrix modulo $\g$}
\begin{algorithmic}[1]\label{alg:HNF}
\REQUIRE $A \in K^{n\times n}$, $\ag_1,\cdots,\ag_n$ , $\g$.
\ENSURE pseudo-HNF $B$, $\bg_1,\cdots,\bg_n$ modulo $\g$. 
\STATE $B\leftarrow A$, $\bg_i\leftarrow \ag_i$, $j\leftarrow n$.
\STATE Normalize $[B_i,\ag_i]_{i\leq n}$ with Algorithm~\ref{alg:normalization}
\WHILE { $j\geq 1$ }
\STATE $i \leftarrow j-1$.
\WHILE { $i\geq 1$ } 
\STATE $\dg \leftarrow b_{i,j}\bg_i + b_{j,j}\bg_j$
\STATE Find $u\in \bg_i\dg^{-1}$ and $v\in \bg_j\dg^{-1}$ such that $b_{i,j}u+ b_{j,j}v = 1$ 
with~\cite[Th. 1.3.3]{cohen2}.
\STATE $(B_i,B_j)\leftarrow (b_{j,j}B_i-b_{i,j}B_j,uB_i + vB_j)$.
\STATE $(\bg_i,\bg_j)\leftarrow (b_{i,j}\bg_ib_{j,j}\bg_j\dg^{-1},\dg)$.
\STATE Normalize $\bg_i,B_i$ with Algorithm~\ref{alg:normalization}.
\STATE Reduce $B_i$ modulo $\g\bg_i^{-1}$ and $B_j$ modulo $\g\bg_j^{-1}$ with Algorithm~\ref{alg:reduction}. 
\STATE $i\leftarrow i-1$.
\ENDWHILE
%\STATE $i\leftarrow j+1$.
%\WHILE {$i\leq n$}
%\STATE Find $q\in \bg_i\bg^{-1}_j$ such that $b_{i,j} - q$ is small.
%\STATE $B_i\leftarrow B_i-qB_j$, $i\leftarrow i+1$.
%\ENDWHILE
\STATE $j\leftarrow j-1$.
\ENDWHILE
\RETURN $(\bg_i)_{i\leq n}$, $B$.
\end{algorithmic}
\end{algorithm}

The normalization and reduction at Steps 10-11 allows us to keep the size of the $B_i$ and of the $\bg_i$ 
reasonably bounded by invariants of $K$ and the dimension of the module. By doing so, we give away some 
information about the module $M$. Indeed, at the end of Algorithm~\ref{alg:HNF}, we obtain a pseudo-basis 
$[(B_i)_{i\leq n},(\bg_i)_{i\leq n}]$ such that 
%$$\sum_{i\leq n} \bg_iB_i \subseteq M + \sum_{i\leq n}\g e_i,$$
$$\forall i\leq n\  \bg_iB_i \subseteq M + \g e_i,$$
where $e_i := (0,0,\cdots,1,0,\cdots,0)$ is the $i$-th vector of the canonical basis of $K^n$. 
Let $M_i\subseteq \OK^{n-i}$ be the $\OK$-module defined by 
$$\ag_1(a_{1,n-i},\cdots , a_{1,n}) + \cdots + \ag_n(a_{n,n-i},\cdots,a_{n,n}),$$
and $\g(M_i)$ its determinantal ideal. The operations performed at Step 6 to 10 in Algorithm~\ref{alg:HNF} preserve 
$\g(M_i)$ while after Step~11, our pseudo-basis $[(B_i)_{i\leq n},(\bg_i)_{i\leq n}]$ only defines a module $M'\subseteq\OK^n$
satisfying 
$$\g(M'_i) + \g = \g(M_i) + \g.$$
This property is the equivalent of the integer case when the HNF is taken modulo a multiple $D$ of the determinant of the 
lattice. To recover the ideals $\cg_i$ of the pseudo-HNF of $M$, we first notice that 
\begin{align*}
\forall i,\g(M_i) + \g &= \cg_{n-i}\cdots\cg_n + \g \\
&= \cg_{n-i}\cdots\cg_n + \cg_1\cdots \cg_n \\
&= \cg_{n-i}\cdots\cg_n.
\end{align*}
On the other hand, $\g(M'_i) + \g = \bg_{n-i}\cdots\bg_n + \g$. Thus, we have 
$$\forall i,\ \bg_{n-i}\cdots\bg_n +\g= \cg_{n-i}\cdots\cg_n,$$
which allows us to recursively recover the $\cg_i$ from the $(\bg_j)_{j\geq i}$ and $\g$. Indeed, as in the integer case, 
it boils down to taking 
$$\cg_i = \frac{\g}{\prod_{j > i}\cg_j} + \bg_i.$$
To do so, we keep track of $\g_i := \frac{\g}{\prod_{j > i}\cg_j}$ throughout Algorithm~\ref{alg:Euclidian}
that reconstruct the actual pseudo-HNF from its modular version. At each step we set 
$$\cg_i\leftarrow \bg_i + \g_{i}.$$
This replacement of the ideals in the pseudo-basis defining our module impacts the corresponding vectors 
in $K^n$ as well. In particular, we require that the diagonal elements all be 1. Do ensure thus, we find $u\in \bg_i\cg^{-1}_i,\ v\in \g_{i}\cg^{-1}_i$ such that $u + v = 1$ wich implies that 
$$\cg_i(uB_i + ve_i)\subseteq \bg_iB_i + \g_ie_i,$$
where the $i$-th coefficient of $uB_i + ve_i\in K^n$ is 1 and the coefficient of index $j>i$ in $uB_i + ve_i$
are 0. Then we set 
$$W_i\leftarrow uB_i\bmod \g_i\cg^{-1}_i,$$
and observe that $uB_i + ve_i = W_i + d_i$ where the coefficients of $d_i\in\left(\g_i/\cg_i\right)^n$ of 
index $j > i$ are 0. The vector $d_i$ satisfies $\cg_id_i\subseteq \g_id'_i$ where $d'_i\in\OK^n$ with coefficients $j>i$ equal to 0. This allows us to state that 
$$\cg_i W_i \subseteq \bg_iB_i + \g_ie_i  + \cg_id_i \subseteq M + \g_ie_i  + \g_id'_i \subseteq M + \g_iD_i,$$
where the coefficients of $D_i\in\OK^n$ of index $j>i$ equal 0. We now want to prove that 
$\cg_iW_i\subseteq M$. To do this, we prove that $\g_iD_i\subseteq M$. 

\begin{lemma}\label{lem:1}
Let $M = \ag_1A_1 + \cdots \ag_nA_n\in\OK^n$, then we have 
$$\g(M)\OK^n \subseteq M$$ 
\end{lemma}

\begin{proof}
We can prove by induction that if $[(B_i),(\bg_i)]$ is a pseudo-HNF basis of $M$, then 
$$\forall i,\ \g_1\cdots\g_i e_i \subseteq M,$$
where $e_i$ is the $i$-th vector of the canonical basis of $\OK^n$. Our statement immediatly follows.
\end{proof}

We now consider the intersection $N_i$ of our module $M\subseteq \OK^n$ with $\OK^i$. Note that with the 
previous definitions, we have in particular $M = N_i \oplus M_i$. 

\begin{lemma}
Let $i\leq n$ and $D\in\OK^n$ a vector whose entries of index $j>i$ are 0. Then we have 
$$\g_i D \subseteq M.$$
\end{lemma}

\begin{proof}
From Lemma~\ref{lem:1}, we know that $\g_i\OK^i \subseteq N_i$. If $D_i\in\OK^i$ is the first $i$ 
coordinates of $D$, then $\g_i D_i\subseteq N_i$, and as the last $n-i$ coordinates of $D$ are 0, we have 
$$\g_i D \subseteq M.$$
\end{proof}
The module generated by the pseudo-basis $[(W_i),(\cg_i)]$ computed by Algorithm~\ref{alg:Euclidian} is 
a subset of $M$. We ensured that its determinantal ideal $\prod_i\cg_i$ equals the determinantal ideal 
$\g$ of $M$. Let us prove that it is sufficient to ensure that 
$$\cg_1 W_1 + \cdots + \cg_n W_n = M.$$

\begin{lemma}\label{lem:3}
Let $M = \sum_{i\leq n} \ag_i A_i$ and $M' = \sum_{i\leq n} \bg_i B_i$ two $n$-dimensional $\OK$-modules 
such that $M'\subseteq M$ and $\g(M') = \g(M)$. Then necessarily 
$$M = M'.$$
\end{lemma}

\begin{proof}
Let $[(W_i),(\cg_i)]$ be a pseudo-HNF for $M$, and $[(W'_i),(\cg'_i)]$ a pseudo-HNF for $M'$. By assumption, we have $\prod_i\cg_i= \prod_i\cg'_i$, and $M'\subseteq M$. As both matrices $W$ and $W'$ have a lower
triangular shape, it is clear that 
\begin{equation}
 \forall i, \ \sum_{j\leq i}\cg'_jW'_j \subseteq \sum_{j\leq i} \cg_jW_j.\label{eq:mod_inc}
\end{equation}
As the diagonal coefficients of both $W$ and $W'$ are 1, we see by looking at the inclusion in the coefficient $i$ of~\eqref{eq:mod_inc} that $\cg'_i\subseteq \cg_i$. Then as $\g(M) = \g(M')$, we have 
$$\forall i \cg_i = \cg'_i.$$
Now let us prove by induction that 
\begin{equation}
 \forall i,\ \cg_iW_i \subseteq \cg_1W'_1 + \cdots + \cg_iW'_i.\label{eq:rec_mod_inc}
\end{equation}
This assertion is clear for $i=1$ since $W_1 = W'_1 = e_1$. Then, assuming~\eqref{eq:rec_mod_inc} for 
$1,\cdots,i-1$, we first use the fact that 
$$\cg_iW'_i \subseteq \cg_1W_1 + \cdots + \cg_i W_i.$$
In other words, $\forall c'_i\in\cg_i$, $\exists (c_1,\cdots,c_i)\in\cg_1\times\cdots\times\cg_i$ such that 
$$c'_i(w'_{i,1},\cdots,w'_{i,i-1},1) = \left(\sum_{1\leq j\leq i} c_jw_{j,1} , \cdots , c_{i}w_{i,i-1} + c_{i-1} , c_i\right).$$ 
In particular, $c_i = c'_i$, which allows us to state that $\forall c_i\in\cg_i$, 
$\exists (c_1,\cdots,c_{i-1})\in\cg_1\times\cdots\times\cg_{i-1}$ such that 
\begin{align*}
c_i w_{i,i-1} &= c_{i-1}  + c_i w'_{i,i-1} \\
c_i w_{i,i-2} &= c_{i-2}  + c_{i-1} w_{i-1,i-2} + c_iw'_{i,i-2} \\
\vdots\ \  &=\ \  \vdots \\
c_i w_{i,1} &= c_{1} + \cdots + c_{i-1} w_{i-1,1} + c_iw'_{i,1}.
\end{align*}
This shows that 
$$\cg_iW_i \subseteq \cg_1W_1 + \cdots + \cg_{i-1}W_{i-1} + \cg_iW'_i,$$
and since we have $\forall j<i,\ \cg_jW_i\subseteq \sum_{j<i}\cg_jW'_j$, we obtain the desired result.
\end{proof}

Lemma~\ref{lem:3} is a generalization of the standard result on $\Z$-modules stating that if $L'\subseteq L$
and $\det(L) = \det(L')$, then $L = L'$. Although implied in~\cite[Chap. 1]{cohen2}, Lemma~\ref{lem:3} is 
not stated, nor proved in the litterature. Yet, it is essential to ensure the validity of 
Algorithm~\ref{alg:Euclidian}. 

\begin{proposition}
The $\OK$-module defined by the pseudo-basis $[(W_i),(\cg_i)]$ obtained by applying lgorithm~\ref{alg:Euclidian} to the pseudo-HNF of $M$ modulo $\g(M)$ satisfies 
$$\cg_1 W_1 + \cdots + \cg_n W_n = M.$$
\end{proposition} 

\begin{algorithm}[ht]
\caption{Eucledian reconstruction of the pseudo-HNF}
\begin{algorithmic}[1]\label{alg:Euclidian}
\REQUIRE $B \in K^{n\times n}$, $\bg_1,\cdots,\bg_n$ output of the pseudo-HNF modulo $\g$ for 
$M\subseteq \OK^n$.
\ENSURE A pseudo HNF $W$,$\cg_1,\cdots,\cg_n$ for $M$. 
\STATE $j\leftarrow n$ , $\g_j\leftarrow \g$.
\WHILE { $j\geq 1$ }
\STATE $\cg_j\leftarrow \bg_j + \g_j$.
\STATE Find $u\in \bg_j\dg^{-1}$ and $v\in \g\cg^{-1}_j$ such that $u + v = 1$.
\STATE $W_j\leftarrow uB_j\bmod \g\cg^{-1}_j$.
\STATE $\g_j \leftarrow \g_j\cg^{-1}_j$.
%\STATE $i\leftarrow j+1$.
%\WHILE {$i\leq n$}
%\STATE Find $q\in \bg_i\bg^{-1}_j$ such that $w_{i,j} - q$ is small.
%\STATE $W_i\leftarrow W_i-qW_j$, $i\leftarrow i+1$.
%\ENDWHILE
%\STATE $\g\leftarrow \g\dg^{-1}$.
\STATE $j\leftarrow j-1$.
\ENDWHILE
\RETURN $W,(\cg_i)_{i\leq n}$.
\end{algorithmic}
\end{algorithm}

\section{Complexity}\label{sec:complexity}

Let us assume that we are able to compute the determinantal ideal $\g$ of our module $M$ in polynomial time 
with respect to the bit size of the invariants of the field and of $S(\g)$. In this section, we show that 
Algorithm~\ref{alg:HNF} and Algorithm~\ref{alg:Euclidian} are polynomial wih respect to the same parameters.
This result is analogous to the case of integers matrices. Indeed, the only thing we need to verify is that 
the size of the elements remain remains reasonably bounded during the algorithm. The number of operations is 
the same as in the integer case. 

In Algorithm~\ref{alg:HNF}, the coefficient explosion is prevented by the modular reduction of Step~11. It ensures that 
$$\forall i<j, \ \|b_{i,j}\|\leq d^{3/2}2^{d/2}\Nm(\g\bg_i^{-1})^{1/d}\sqrt{|\Delta_K|}.$$
In addition, since $\bg_i$ is integral, we have 
$$\forall i<j, \ \|b_{i,j}\|\leq d^{3/2}2^{d/2}\Nm(\g)^{1/d}\sqrt{|\Delta_K|}.$$
This is not enough to prevent the explosion since $b_{i,j}$ might not be integral. Therefore, there is a 
minimal $k\in\Z_{>0}$ such that $kb_{i,j}\in\OK$, which we need to bound to ensure that $S(b_{i,j})$ remains bounded as well. We know that $b_{i,j}\bg_i\subseteq\OK$, and that $\bg_i$ is integral. Thus, 
$\Nm(k)\mid \Nm(\bg_i)$, which in turns implies that $k\leq \Nm(\bg_i)$. As on the other hand, the 
normalization of Step~10 ensures that $\Nm(\bg_i)\leq 2^{d^2/2}\sqrt{|\Delta_K|}$, we conclude that 
\begin{align*}
k &\leq 2^{d^2/2}\sqrt{|\Delta_K|}\\
S(b_{i,j}) &\leq \log(k) + d\log\left(2^{3d/2}\|kb_{i,j}\|\right) \\ 
&\leq \log\left(2^{d^2/2}\sqrt{|\Delta_K|}\right) + d\log\left(d^{3/2}2^{2d+d^2/2}\Nm(\g)^{1/d}|\Delta_K|\right).
\end{align*}

In Algorithm~\ref{alg:HNF}, we last manipulate $B_j$ and $\bg_j$ when the index $j$ is the pivot. In that 
case, we cannot use the normalization to bound the size since we require that $b_{j,j} = 1$. Fortunately, for each $i$. we 
reduced $B_i$ modulo $\g\bg_i$, which means that 
$$\forall i, \ \|b_{i,j}\|\leq d^{3/2}2^{d/2}\Nm(\g\bg_i^{-1})^{1/d}\sqrt{|\Delta_K|}.$$
In addition, the arithmetic-geometric tells us that $\|b_{i,k}\|\geq \sqrt{d}\Nm(b_{i,k})^{1/d}$, which in turn implies that 
$$\forall i, \Nm(b_{i,j}\bg_i)\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}.$$
As we know that $\Nm(b_{i,j}\bg_i + b_{j,j}\bg_j) \leq \max(b_{i,j}\bg_i,b_{j,j}\bg_j)$, we therefore know that Step~9 ensures that 
$\Nm(\bg_j)\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}$, which allows us to bound the size of the denominators in the $j$-th row 
the same way we did for the indices $i<j$
\begin{align*}
k &\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}\\
S(b_{i,j}) &\leq \log(k) + d\log\left(2^{3d/2}\|kb_{i,j}\|\right) \\ 
&\leq \log\left(d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}\right) + \log\left(d^{d+3/2}2^{2d+d^2/2}\Nm(\g)^{1/d}|\Delta_K|^{(d+1)/2}\right).
\end{align*}

The Euclidian reconstruction of Algorithm~\ref{alg:Euclidian} can be seen as another pivot operation 
between the two one-dimensional $\OK$-modules $\bg_j B_j$ and $\g_je_j$. We can 
therefore bound the entries of $W$ by the same method as for Step~6-11 of Algorithm~\ref{alg:HNF}, we the 
extra observation 
$$\Nm(\g_j)\leq \Nm(\g).$$
Therefore, we showed that we could bound the size of the objects that are manipulated 
throughout the algorithm by values that are polynomial in terms of $n$, $d$, $S(\g)$ and $\log(|\Delta_K|)$. The complexity of 
the HNF algorithm is therefore polynomial in these values.

\section{Computing $\g$}

Let us assume that $A\in\OK^{n\times n}$. If it is not the case, then we need to multiply by the common 
denominator $k$ of the entries of $A$ and return $\det(kA)/k^n$. In this section, we describe how to compute $\g$ in polynomial time with respect to $n$, $d$, $\log|\Delta_K|$ and the size of the entries of $A$. The idea is to compute $\det(A)\mod (p)$ for a sufficiently large prime number $p$. In practice, one might 
prefer to compute $\det(A)\mod (p_i)$ for several prime numbers $p_1,\cdots,p_l$ and recombine the values 
via the chinese remainder theorem, but for the sake of simplicity, we only describe that procedure for a 
single prime. Once $\det(A)$ is computed in polynomial time, we return 
$$\g = \det(A)\cdot \ag_1\cdots \ag_n.$$

The first step consists of evaluating how large $p$ should be to ensure that we recover $\det(A)$ 
uniquely. We make the assumption that $p$ does not split totally in $K$, that is $\Nm((p))\leq p^{d-1}$. 
The LLL reduction modulo $(p)$ returns $\overline{\det(A)}$ such that 
$$\|\overline{\det(A)}\| \leq d^{3/2}2^{d/2}\Nm((p))^{1/d}\sqrt{|\Delta_K|}\leq p^{(d-1)/d}d^{3/2}2^{d/2}\sqrt{|\Delta_K|}.$$
Assume that a bound on $\|\det(A)\|$ is known, and that $p$ is large enough to ensure that 
$\|\det(A)\|\leq p^{(d-1)/d}d^{3/2}2^{d/2}\sqrt{|\Delta_K|}$ as well. Now we need to prove that 
$\det(A) = \overline{\det(A)}$. We know that there exists $k\in\Z$ such that 
$$\det(A) = \overline{\det(A)} + kp.$$ 
In addition, if $\overline{\|\det(A)\|} = \sum_i \overline{a_i}\omega_i$, then from~\cite[Lem. 2]{stehle_fieker_LLL}, 
we have  
$$\forall i,\ |\overline{a_i}| \leq 2^{3d/2}\|\overline{\det(A)}\|\leq 2^{2d}p^{(d-1)/d}d^{3/2}\sqrt{|\Delta_K|}.$$
Without loss of generality, we can assume that $\omega_1 = 1$. We now show that if $p$ is large enough, then 
the first coefficient of $\det(A)$ will be too large for the condition on $\|\det(A)\|$ to be satisfied, 
unless $k = 0$. We write $\det(A) = \sum_i a_i\omega_i$. In particular, $a_1 = \overline{a}_1 + kp$, and 
if $k\neq 0$ and $p$ is chosen large enough to satisfy 
$$\log(p) > d\log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right), $$
then we have $|a_1| > p/2$. As we know that $|a_1|\leq 2^{3d/2}\|\det(A)\|$, this gives us on the other 
hand 
$$\log(p) < \log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right),$$
which is impossible. We conclude that is $p$ is a non totally split prime in $K$ satisfying 
\begin{align*}
\log(p) &> d\log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right) \\
\log(p) &\geq \frac{d}{d-1}\left( \log\left(\|\det(A)\|\right) - \frac{3}{2}\log(d) - \frac{d}{2} \right),
\end{align*}
then $\overline{\det(A)} = \det(A)$. 

Now, let us see how to find a bound on $\|\det(A)\|$. We first compute an upper bound on $|\sigma(\det(A))|$ for the $d$ complex embeddings $\sigma$ of $K$ via Hadamard's inequality and then we deduce a bound on $\|\det(A)\|$. Let $\sigma : K\rightarrow\mathcal{C}$, we know from Hadamard's inequality that 
$$|\sigma(\det(A))|\leq B^n n^{n/2},$$
where $B$ is a bound on $\sigma(a_{i,j})$. Such a bound can be derived from the size of the coefficient 
of $A$ by using 
$$\forall x, \ \forall i\ |\sigma_i(x)| \leq \left(\max_j|x_j|\right)d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}.$$
This way, we see that $B := 2^{\max_{i,j}S(a_{i,j})}d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}$ suffices. Then, our 
bound on $\|\det(A)\|$ is simply 
$$\|\det(A)\| \leq \sqrt{n} 2^{\max_{i,j}S(a_{i,j})}d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}.$$

\begin{algorithm}[ht]
\caption{Computation of $\det(A)$}
\begin{algorithmic}[1]
\REQUIRE $A\in \OK^{n\times n}$
\ENSURE $\det(A)$.
\STATE $B_1\leftarrow d\log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right)$.
\STATE $B_2 \leftarrow \frac{d}{d-1}\left( \log(n)/2 +  \max_{i,j}(S(a_{i,j})) \right)$.
\STATE Let $p\in\N$ be the smallest non totally split prime above  $\max(B_1,B_2)$ and $(\p_i,e_i)_{i\leq g}$ such that $(p)=\prod_{i\leq g}\p_i^{e_i}$. 
\FOR {$\p_i\mid(p)$}
\STATE Compute $\det(A)\bmod \p_i$.
\ENDFOR
\STATE Recover $\det(A)\bmod (p)$ via 
\[   \left. \begin{array}{ccc}
    \OK/\p_1^{e_1}\times \cdots \times \OK/\p_g^{e_g}     & \longrightarrow  &   \OK/(p)\\
    (\det(A)\bmod \p_1^{e_1},\cdots ,\det(A) \bmod \p_g^{e_g})   & \longmapsto & \det(A)\bmod (p). \end{array} \right. \] 
\RETURN $\det(A)$.
\end{algorithmic}
\end{algorithm}

\section{Intersection of $\OK$-modules}

In this section, we prove that we can intersect $\OK$-modules in polynomial time with respect to the 
invariants of $K$ and of the sizes of the modules. The algorithm described in~\cite[Alg. 1.5.1]{cohen2} 
allows us to intersect two modules of $\OK^{n\times n}$ given by their pseudo-basis at the cost of the 
computation of the pseudo-HNF of a module in $\OK^{n\times n}$. 

 Let $M,N$ are two modules over a Dedekind domain given by $A,(\ag_i)_{i\leq l+1}$ and $B,(\bg_i)_{i\leq l+1}$, and let $C$ be the pseudo-matrix given by
\[ \left( \begin{array}{cc}
A & A  \\
0 & B  \end{array} \right),\]
and $\cg_1,\cdots,\cg_{2(l+1)}$. Then the upper left $(l+1)\times (l+1)$ minor for the HNF of $C$, together with $\cg_1,\cdots,\cg_n$ represent $M\cap N$ (see the proof of~\cite[Alg. 1.5.1]{cohen2}).

It is easy to see that $\g(C) = \g(A)\cdot\g(B)$. Therefore, the cost of Algorithm~\ref{alg:HNF} applied 
to $(C , (\cg_i)_{i\leq 2n})$ is polynomial in $n$, $d$, $\log|\Delta_K|$, $S(\g(M))$ and $S(\g(N))$. We showed that we could bound the output of Algorithm~\ref{alg:HNF} by a polynomial expression in the 
field invariants and $\g(C)$. Namely, the coefficients $\left(\frac{n_{i,j}}{d_{i,j}}\right)_{i,j\leq 2n}$ of the resulting matrix in $K^{2n\times 2n}$ satisfy 
\begin{align*}
|d_{i,j}|&\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}\\
S(n_{i,j}) &\leq \log\left(d^d 2^{d^2/2} \Nm(\g(C))^d |\Delta_K|^{d/2}\right) + \log\left(d^{d+3/2}2^{2d+d^2/2}\Nm(\g(C))^{1/d}|\Delta_K|^{(d+1)/2}\right),
\end{align*}
while the ideals $\cg_i$ are integral of norm bounded by $\Nm(\g(C))$. Therefore, the cost of intersecting 
$k$ modules $M_1,\cdots,M_k$ is polynomial in $k$, $d$, $\log|\Delta_K|$, and the size of 
$$\g:= \g(M_1)\cdots\g(M_k),$$
since after each intersection of two modules the size of our output is bounded by absolutes bounds.
%which bounds $S(b_{i,j})$ since $S(b_{i,j}) = O(\|b_{i,j}\|)$. 
%Let us prove first that the entries matrix $B$ coming out of Algorithm~\ref{alg:HNF} are reasonably bounded. In the following, we work under the assumption that our $\OK$-module is in $\OK^n$ whereas in general, it can be in $K^n$. The reduction in Step 7 in Algorithm~\ref{alg:HNF} 
%allows to derive a bound on the size of the one-dimensional $\OK$-module 
%$$\bg_i B_i,$$
%for $i\leq n$. Indeed, at the end of Algorithm~\ref{alg:HNF}, each $B_i\in K^n$ is 
%reduced modulo $\g\bg_i^{-1}$. Let $k\leq n$, and $b_{i,k}\in K$ be one of the coefficients of the row $B_i$. We use~\cite[Alg 1.4.13]{cohen2} to reduce $b_{i,k}\in K$ modulo $\g\bg_i^{-1}$. It consists of computing an LLL-reduced basis $r_1,\cdots , r_d$ of $\g\bg_i^{-1}$, then to decompose
%$$b_{i,k} = \sum_{j\leq d} x_jr_j, $$
%where $x_i\in\Q$, and then return 
%$$\overline{b_{i,k}} = b_{i,k} - \sum_{j\leq d}\lfloor x_j \rceil r_j.$$
%Let $I$ be an integral ideal of $\OK$, and $\lambda_1,\cdots,\lambda_d$ its first $d$ successive minimas. From Minkowski's second theorem, we know that 
%$$\prod_{j\leq d} \lambda_j \leq d^{d/2} \Nm(I)\sqrt{\Delta_K}.$$
%In the meantime, the arithmetic-geometric mean applied to any $x\in I$ such that $\|x\| = \lambda_1$ implies that 
%$$1\leq \Nm(I)^{2/d} \leq \Nm(x)^{2/d} \leq \frac{\|x\|^2}{d}, $$
%and thus $\lambda_1 \geq \sqrt{d}\Nm(I)^{1/d}$. So in particular, every $\lambda_i$ has to satisfy 
%$$\lambda_i\leq \sqrt{d}\Nm(I)^{1/d}\sqrt{\Delta_K}.$$
%The LLL~\cite{LLL} algorithm allows us to compute a basis $(r_j)_{j\leq d}$ for $I$ that satisfies
%$$\|r_j\|\leq 2^{d/2}\lambda_i\leq 2^{d/2}\sqrt{d}\Nm(I)^{1/d}\sqrt{\Delta_K}.$$ 
%The same holds for a fractional ideal $\ag$ of $K$. Indeed, by definition, there is a $k\in \Z$ such that $I = k\ag$ is an ideal of $\OK$, and if $(r_j)_{j\leq d}$ is an LLL-reduced basis for $\ag$, then $(kr_j)_{j\leq d}$ is an LLL-reduced basis for $I$ and we have 
%\begin{align*}
% k\|r_j\| = \|kr_j \| &\leq  2^{d/2}\sqrt{d}\Nm(k\ag)^{1/d}\sqrt{\Delta_K} \\
%&\leq  2^{d/2}\sqrt{d}\Nm((k))^{1/d} \Nm(\ag)^{1/d}\sqrt{\Delta_K} \\
%&\leq  k\cdot 2^{d/2}\sqrt{d} \Nm(\ag)^{1/d}\sqrt{\Delta_K}.
%\end{align*}
%Then, as $\lfloor x_j \rceil r_j\leq 1$, we see that 
%$$\|\overline{b_{i,k}}\|\leq d\max_j\|r_j\|\leq d^{3/2}2^{d/2}\Nm(\g\bg_i^{-1})^{1/d}\sqrt{\Delta_K}.$$
%We can therefore deduce a bound for each coefficient $b_{i,k}$ and each ideal $\bg_i$ that only depends 
%on the invariants of the fiels and the determinantal ideal
%$$\Nm(\bg_i)^{1/d}\|b_{i,k}\|\leq d^{3/2}2^{d/2}\Nm(\g)^{1/d}\sqrt{\Delta_K}.$$


%In the following, we need a bound on $\Nm(b_{i,k}\bg_i)$. We use the arithmetic-geometric mean to show that $\|b_{i,k}\|\geq \sqrt{d}\Nm(b_{i,k})^{1/d}$, and then we can conclude that 
%$$\forall k\leq n, \Nm(b_{i,k}\bg_i)\leq d^d 2^{d^2/2} \Nm(\Delta_K)^d \Delta_K^{d/2}.$$
%Since we made the assumption that our module $M$ was in $\OK$, we know that $\g\subset \OK$, so even after the reduction at Step 7 of Algorithm~\ref{alg:HNF}, we still have $b_{i,k}\bg_i\subset \OK$. The fact that the $b_{i,k}\bg_i$ are integral ideals with a bounded norm allows us to bound the norm of $\g\dg^{-1}$ throughout Algorithm~\ref{alg:Euclidian}. Indeed, for each $1\leq j\leq n$, the entries of the $j$-th row $W_j$ of $W$ are reduced modulo $\g\dg^{-1}$. This reduction, performed at Step 5 of Algorithm~\ref{alg:Euclidian} ensures that the entries of $W$ remain reasonably bounded, and that the arithmetic operations on $W$ are of polynomial complexity. By induction, we see that $\g$ at the $j$-th step has the form
%$$\frac{\g_0}{b_{j,j}\bg_j(b_{j-1,j-1}\bg_{j-1}(\cdots b_{2,2}\bg_2(b_{1,1}\bg_1 + \g_0) + \cdots + \g_0) + \g_0} := \frac{\g_0}{\cg},$$ 
%where $\g_0$ is the determinantal ideal before the first modification. Both the numerator and the denominator of $\g$ are integral ideals. The numerator $\g_0$ is given as input, whereas the denominator $\cg$ satisfies
%$$1\leq \Nm(\cg) \leq \left(\prod_{j\leq n} \Nm(b_{j,j}\bg_j)\right) \Nm(\g_0)\leq d^{nd} 2^{nd^2/2} \Nm(\Delta_K)^{nd} \Delta_K^{nd/2}\Nm(\g_0).$$
%This allows us to bound the size of the coefficients of $W$ after the modular reduction at Step 5 of Algorithm~\ref{alg:Euclidian}.
%Indeed, they satisfy 
%$$\|w_{i,j}\|\leq d^{3/2}2^{d/2}\Nm(\g_0)^{1/d}\sqrt{\Delta_K}.$$


\bibliography{paper}


\end{document}
